package com.leetcode.algs4.sort;

import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/6/14 16:29
 */
public class QuickSort {

    // 快速排序核心思想：找一个基准值，将数据切割成两部分
    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    // [-9,78,0,23,-567,70]
    public static void quickSort(int[] arr, int l, int r) {
        int left = l;
        int right = r;
        // 中轴值
        int middle = (left + right) / 2;
        int pivot = arr[middle];

        int temp; // 用于交换两个值
        // 比pivot大的放到右边，比pivot小的放到左边
        while (left < right) {
            // 在pivot的左边一直找，找到大于等于pivot值，才退出
            while (arr[left] < pivot) {
                left++;
            }
            // 在pivot的右边一直找，找到小于等于pivot值，才退出
            while (arr[right] > pivot) {
                right--;
            }
            // 说明pivot的左右两边的值，已经按照左边全部是小于等于pivot的值，右边全部是大于等于pivot
            if (left >= right)
                break;

            // 交换了值
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;


            // 如果交换完成后，发现arr[left] == pivot。前移
            if (arr[left] == pivot) {
                left++;
            }
            // 如果交换完成后，发现arr[right] == pivot。后移
            if (arr[right] == pivot) {
                right--;
            }
        }

        // 避免出现栈溢出
        if (left == right) {
            left++;
            right--;
        }

        if (left < r) {
            quickSort(arr, l, right);
        }
        if (right > l) {
            quickSort(arr, left, r);
        }
    }
}
